package com.geticsen.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//https://leetcode-cn.com/problems/3sum/
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []
        if (nums == null || nums.length < 3) return result;
        int L, R;
        //排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //当前如果大于零则 L R i 之和必定大于0则返回结果
            if (nums[i] > 0) return result;
            //过滤重复
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            L = i + 1;
            R = nums.length - 1;
            while (L < R) {
                //相等则加入结果集
                if (nums[i] + nums[L] + nums[R] == 0) {
                    result.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    //过滤掉重复
                    while (L < R && nums[L] == nums[L + 1]) ++L;
                    while (L < R && nums[R] == nums[R - 1]) R--;
                    ++L;
                    --R;
                } else if (nums[i] + nums[L] + nums[R] > 0) {
                    //相加大于零则右侧太大
                    R--;
                } else {
                    //相加小于零则左侧太小
                    ++L;
                }
            }
        }
        return result;
    }
}
